순차열 컨테이너는 데이터 관리에 유용하지만, 대다수 프로그램에서 순차열 컨테이너가 편리한 데이터 엑세스 도구는 아니다. 이름과 주소를 관리할때도 순차열 컨테이너는 적합하지 않을수 있음.

연관 컨테이너는 객체를 객체와 연관된 키 값으로 위치를 정한다. 키값은 기본타입일수도 있고, 클래스 객체일수도 있다.

연관 컨테이너

  1. map <K, T> 키/객체 쌍을 캡슐화한 pair<const K, T> 타입을 원소로 지정한다. 키는 유일해야하며, 키 값만 다르다면 중복 객체도 저장가능
  2. multimap<K, T> map<K, T>와 같지만, 중복키를 허용한다. 원소들의 순서는 키를 비교해서 결정.
  3. unordered_map<K, T> pair <const K, T> 객체를 키값으로 직접 정렬하지 않는다. 원소는 키 값으로 생성된 해시 값으로 사용해 위치가 정해진다. 중복 키는 허용되지 않는다.
  4. unorederd_multimap<K, T> 중복키를 허용한 unordered_map<K, T>

map 컨테이너

map 컨테이너는 원소들을 Key을 기준으로 균형 이진 트리로 저장한다. 임의의 원소를 가져오는 시간은 O(log N)이고, 순차열에서 원소를 가져오는시간은 O(N)이다

  1. 정렬해야 한다.
  2. 많은 자료를 저장하고, 검색이 빨라야 한다
  3. 빈번하게 삽입, 삭제하지 않는다

map 컨테이너 생성

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
map<string, size_t> people; // 이름을 키, 나이를 값으로 저장하는 맵 컨테이너

map<string, size_t> people  { {"A", 1}, {"B", 2}, {"C", 3}}; // 초기화 리스트를 이용한 맵의 초기화
// 이 예제인경우, pair의 타입은 무조건 pair<string, size_t>이어야 된다.

// utility 헤더 make_pair을 이용해서 편리하게 조합하룻도 있다.
map<string, size_t> people  { make_pair("A", 1), make_pair("B", 2), make_pair("C", 3)};
// make_pair<>() 호출 반환한 객체는 pair<char const*, int> 가 된다.

map<string, size_t> personnel {people}; // 복제는 다음과같이할수있다.

// 범위를 지정해서 복제할수도 있다.
map<string, size_t> personnel { begin(people), end(people)};

// map의 이터레이터는 양방향 반복자이기 때문에, 증가, 감소가 가능하다. 랜덤엑세스는 안된다.
// iter = iter + 4는 불가능

map 컨테이너 원소 삽입 및 내부 생성

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
map<string, size_t> people;
auto ret_pr_iter = people.insert("Fred", 22);

auto ret_pr = people.insert(make_pair("A", 5));
// first = 삽입된 원소 또는 삽입할 원소의 키와 같은 원소를 가르킴
// second = 삽입성공 및 실패

if(!ret_pr.second)  // 삽입에 실패한경우
    ret_pr.first->second = 48;  // Age만 바꿀수있다.

// pair 생성자
people.insert(pair<const std::string, size_t> {"Bill", 48});

// 만약 원소가 이미 있는지 확인하고 싶다면 insert 리턴보다는 count함수를 활용하는게 좋음.
if(!people.count("Ian"))
    people.insert()
    
map<string, size_t> crowd { {"A", 1}, {"B", 2}, {"C", 3}};
auto iter = begin(people);
std::advance(iter, 4);			// 시작 반복자 + 4
crowd.insert(++std::begin(people), iter);	// people 2,3,4번째에 삽입

// 초기화 리스트를 이용해 원소두개를 넣을수도 있다.
crowd.insert({{"GGG", 100}, {"FFF", 111}});

// initialize_list<>을 이용해 initialize_list<const string, size_t> 타입으로 직접지정해서 넣기도 된다.
initialize_list<pair<string, size_t>> init {{"III", 222}, {"JJJ", 333}};
crowd.insert(init);

// 복제 및 이동연산을 안해도 되는 emplace 연산이 있다.
class Name
{
    string a;
    string b;
}

map<Name, size_t> people;
people.emplace(Name{"Dan", "Druff"}, 77);

// emplace_hint() 는 첫번째 인수로 지정한 반복자를 새 원소 생성을 위한 탐색 시작 위치로 사용된다는 점을 제외하면 emplace와 같다. 단 리턴값이 다르다. 원소가 생성되었는지 직접알수 있는값이 아니다. -> 키가 같은 원소를 가르키는 반복자를 반환해서 그렇다.

원소 접근

map 컨테이너는 역방향 반복자로 접근할수 있다. 키가 없다면 out_of_range Exception이 발생된다.

1
2
3
4
5
6
map<Name, size_t> people;
auto iter = people.at(key);

// operator[]()을 사용해서 가져온다.
auto age = people[Name{"Dan", "Druff"}];  // 키가 없다면 새원소를 생성하게 된다.
people[Name{"Dan", "Druff"}] = 39; // 키에 설정된 값을 39로 설정한다.

pair, tuple 객체 사용하기

tuple 객체는 pair 템플릿을 일반화 한것으로 타입이 다른 객체를 몇개라도 캡슐화한 tuple 템플릿 인스턴스를 정의할수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// C++ 11 매커니즘 사용한 pair 생성
pair<Name, Name> couple {
    piecewise_construct, forward_as_tuple("Jack", "Jones"), forward_as_tuple("Jill", "Smith")
}

// piecewise_construct : 빈 타입으로, 테크나, 마커로 사용된다. pair 생성자 호출과 두 tuple 생성자 호출을 구분하기 위해서 사용한다.
// 각각 투플은 first, second로 사용된다.
// forward_as_tuple은 우측값 참조로 tuple을 생성한다.

int a {1}, b {2};
const auto& c = forward_as_tuple(a,b); // c type : tuple <int&, int&> 참조관계 -> 좌측값 참조
const auto& c = forward_as_tuple(1,2); // c type : tuple <int&&, int&&> 우측값 참조

auto my_tuple = make_tuple(Name {"Peter", "Piper"}, 42, string {"9146267890"});
// 이 투플의 타입은 tuple<Name, int, const char *> 가 된다.

tuple <string, size_t> t1; // 기본생성
tuple<Name, string> t2{Name{"A", "B"}, string{"programmer"} };
tuple<Name, string> copy_t2 {t2}; // 복제생성
tuple<string, string> t3 {"this", "that"}; // 암묵적 변환

//  투플의 원소 얻기
cout << "Name : "<< get<0>(t2) << "Job : " << get<1>(t2) << endl;

// Tuple과 pair 같이 쓰기
// 전역함수 템플릿 tie<>()은 투플에 있는 원소값을 묶어 좌측값에 전송한다. tie<>() 템플릿 타입인수는 함수인수로 추론된다.

auto my_tuple = make_tuple(Name {"Peter", "Piper"}, 42, string {"9146267890"});
Name name{};
size_t age{};
string phone{};
tie(name, age, phone) = my_tuple; // 인수에 대한 참조를 담은 tuple을 반환한다.

// 겸해서 사용하기
using Name = std::pair < string, string >;                 // 이름 pair를 정의
using DOB = std::tuple <size_t, size_t, size_t>;           // 월, 일, 연도 tuple
using Details = std::tuple < DOB, size_t, string > ;       // 출생일(DOB), 키(인치), 직업
map<Name, Details> People;

people.emplace(std::make_pair(Name {first, second}, std::make_tuple(dob, height, occupation)));

우측값 참조란 기능이 추가되어 메모리의 “복사”가 아니라 “이동”이 가능해 졌다는것!!!

우측값 참조

Unordered_map 컨테이너

해쉬테이블

헤쉬테이블은 Key, Value로 갖는 자료구조로, 주어진 키로 적합한 값을 찾는 자료구조다. 주어진 키를 해쉬값으로 변환하고 해쉬값을 인덱스로 바꾸어 원하는 값 (버켓)을 찾아낸다.

검색성능 : 최악 O(N), 평균 O(1)

해쉬테이블의 예

예전에 만들어본 간단 해쉬테이블

STL 해싱

functional에 hash<K> 템플릿의 특수화가 정의되어 있음.

hash<K> 인스턴스의 operator()()맴버는 타입 K만 인수 받아서 해시 값을 size_t 타입으로 변환한다.

  • Exception을 던지면 안된다.
  • 키가 같으면 해시값도 같아야된다.
  • 다른키일때 충돌할 가능성이 매우 적어야된다.
1
2
3
4
hash<int> hash_int;
vector<int> n {-5, -2, 2, 5, 10};

transform(begin(n), end(n), ostream_iterator<size_t>(cout, " "), hash_int);

이제 제대로 사용해보기

지원하는 해시함수가 반드시 필요한데, 직접 정의한 클래스 타입의 객체를 키로 사용한다면, 해당 타입의 객체에 맞는 해시함수를 만들어야 된다.

STL에서 hash<T>특수화로 지원되는 타입의 객체가 키라면 컨테이너는 키에 대한 해시 값을 생성하는데 이 특수화를 이용할수 있다.

  1. 많은 자료를 저장하고, 검색 속도가 빨라야 한다.

  2. 너무 빈번하게 자료를 삽입, 삭제 하지 않는다.

버컷은 해시테이블에 저장되는 항목들을 말한다.

원소 저장방식에 영향을 주는 요소

  1. 컨테이너의 버킷의 갯수, 버킷 갯수에 기본값이 있겟지만, 초기 갯수 지정할수 있음.
  2. 로드 펙터(load factor) 버킷당 저장된 원소의 평균 갯수를 말한다. 컨테이너의 원소 개수를 버킷 개수로 나눈값
  3. 로드펙터의 최대값. 기본값은 1.0이지만 로드펙터의 상한값을 지정한다. 최댓값에 도달한다면, 더 많은 버킷을 할당하기 위해 메모리 공간을 할ㄷ당한다. 보통 이과정은 컨테이너에 있는 원소들에 대해 재해싱하게 된다.

unordered_map은 상등관계를 위해 키를 비교할수 있어야 된다. 컨테이너에 이미 같은 키가 있을때 둘 이상의 원소가 담긴 버킷에서 특정 원소를 식별하고 결정할수 있으려면 키 비교가 반드시 필요

functional 헤더의 equal_to<K>을 사용할것. 키에 == 연산자 적용한다(상등관계 ==로 값을 찾는다.). map 컨테이너 같은 경우 동등관계로 위치가 같은지 판단한다. (<, > 로 값을 찾는다.)

컨테이너 생성 및 관리

키 타입 K를 hash<K> 인스턴스로 해시할수 있고, == 연산자를 이용해 키를 비교할수만 있다면 해당 컨테이너는 사용가능.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
unordered_map<string, size_t> people { {"Jan", 44}, {"Jim", 33}, {"Joe", 99}};
// pair<string, size_t> 원소를 담는 컨테이너 생긴다.
// equal_to<string>() 으로 키를 비교하며 상등관계 판별
// 해시를 위해 hash<string> 특수화 인스턴스를 사용

// 컨테이너에 저장할 원소의 갯수를 어느정도 알고있다면 버킷의 갯수를 지정가능하다.
unordered_map<string, size_t> people {{ {"Jan", 44}, {"Jim", 33}, {"Joe", 99}},  10};

// 반복자로 정의한 pair 객체들의 범위를 내용으로 채운 컨테이너도 생성가능
// 범위가 요구타입으로 된 pair 라면 어떤 객체든 사용가능
vector<pair<string, size_t>> folks{ {"Jan", 44}, {"Jim", 33}, {"Joe", 99}};
unordered_map<string, size_t> neighbors {begin(folks), end(folks), 500}; // 버킷 500개 할당

// 해시 함수 지정
class Name
{
    size_t hash() const
    {
        return std::hash<string>()(first+second);
    }
    bool operator=(const Name& name) const
    {
        return first == name.first && second == name.second;
    }
    ....
}
class Hash_Name
{
 public:
  	size_t operator()(const Name& name) const { return name.hash(); }  
}

unordered_map<Name, size_t, Hash_Name> people
{
{{{"Ann", "Ounce"} 25}, {{"Bill", "Bao"}, 46}, {{"Jack", "Spart"}, 77}}, // 원소들
500,
Hash_Name()
};
// 원소 - pair<Name, size_t>
// 500개 버킷
// 해시 함수

원소 삽입, 삭제, 접근과 버킷 접근

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
unordered_map<string, size_t> people;
// 삽입 1.
auto ret_pr = people.insert(pair<string, size_t> {"A", 1});
// ret_pr second가 true라면 삽입성공, first는 원소를 가르키는 반복자

// 삽입 2. 원하는 곳에 삽입
people.insert(ret_pr.first, person); // 반복자에 따라 컨테이너에 따라 힌트가 된 ret_pr을 따를지 안따를지모른다. 여기서 리턴하는 값은 삽입에 실패 및 성공한 반복자를 리턴한다.

// 삽입3. 초기화 리스트 삽입 -> 반환값 없음.
people.insert({{"B", 1}, {"C", 2}});

// 삽입4. 원소 범위 삽입
unordered_map<string, size_t> folks;
folks.insert(begin(people), end(people));

// 원소접근 -> 암묵적
people["A"] = 22; // A 22로 설정
people["B"] = people["A"]; // B의 값을 A로 설정
++people["C"]; // C의 값 증가

// 원소접근 -> 명시적
people.at("A");

// unordered map은 반복자를 이용가능해서 range based for 문으로 원소 접근이 가능하다.
for(const auto& person : people)
    cout << person.first << " is " << person.second << endl;

// 원소 삭제
// map의 erase()와 동일
// 리턴 : 키 발견 못함 0
//		  다음 원소를 가르키는 반복자 리턴한다. 물론 범위지정해서 제거하는것도 가능하다.


// 버킷 접근
auto iter = people.begin(1); // 두번째 버킷에 대한 반복자 리턴

size_t index {1}; // 두번째 버킷에 대한 루프출력
for(auto iter = people.begin(index); iter != people.end(index); ++iter)
    cout << iter->first << " is " << iter->second << endl;

// 버킷의 사이즈는 bucket_count()로 가져올수 있고 bucket_size()는 해당 지정 버컷에 있는 원소의 갯수를 반환한다. bucket() 함수는 인수로 전달한 키에 해당하는 원소가 담긴 버킷의 인덱스를 반환한다.
string key {"A"};
if(people.find(key) != end(people))
    cout << "The Number of Elements in the Bucket Containing " << key << " is " 
    << people.bucket_size(people.bucket(key)) << endl;